class Solution
{
public:
    long long maximumSumOfHeights(vector<int> &maxHeights)
    {
        int n = maxHeights.size();
        vector<long long> dpLeft(n, 0);
        vector<long long> dpRight(n, 0);

        stack<long long> s;
        for (long long i = 0; i < n; ++i)
        {
            while (!s.empty() && maxHeights[s.top()] >= maxHeights[i])
            {
                s.pop();
            }
            if (s.empty())
            {
                dpLeft[i] = maxHeights[i] * (i + 1);
            }
            else
            {
                dpLeft[i] = dpLeft[s.top()] + maxHeights[i] * (i - s.top());
            }
            s.push(i);
        }

        s = stack<long long>();
        for (long long i = n - 1; i >= 0; --i)
        {
            while (!s.empty() && maxHeights[s.top()] >= maxHeights[i])
            {
                s.pop();
            }
            if (s.empty())
            {
                dpRight[i] = maxHeights[i] * (n - i);
            }
            else
            {
                dpRight[i] = dpRight[s.top()] + maxHeights[i] * (s.top() - i);
            }
            s.push(i);
        }
        long long result = 0;
        for (long long i = 0; i < n; ++i)
        {
            result = max(result, dpLeft[i] + dpRight[i] - maxHeights[i]);
        }
        return result;
    }
};